This is a clinical phase I/II trial to determine the safety and efficacy of anal-region ONYX-015 injections in HIV-infected individuals. All patients will have high-grade squamous intraepithelial neoplasia (HSIL) and HIV infection with a CD4 count of greater than 100. Multi-day (5) injections may be repeated monthly for up to 3 months. Local and systemic toxicity will be quantitated and reported. The response rate will be defined histologically. Correlative studies will be done on tissue to determine the association of p53 mutations, HPV integration, HPV subtype, immune status, and other factors on the outcome variables. The GCRC will be used for the outpatient treatments as has been the case for all prior phase I/II clinical trials of HIV anal dysplasia performed at UCSF. This will facilitate handling of the attenuated adenovirus and the specimens obtained from patients on study.